链式双端队列Deque——数据结构系列教程(c++版)

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    学生索引结构体(Student)
//
//========================================================================================================================================================================
struct StudentIndex {
    int id;// 学号
    int row;// 行号

    bool operator<(const StudentIndex& other) const { return id < other.id; }
    bool operator>(const StudentIndex& other) const { return id > other.id; }
    bool operator==(const StudentIndex& other) const { return id == other.id; }
    bool operator!=(const StudentIndex& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const StudentIndex& i) {
        os << "[" << i.id << ", " << i.row<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//                                                                    迷宫坐标结构体(Pos)
//========================================================================================================================================================================
struct Pos{
    int x;     //x坐标
    int y;    //y坐标
    int step; //步数
};

//========================================================================================================================================================================
//                                                                    打印任务结构体(PrintTask)
//========================================================================================================================================================================
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

#endif // ENTITYS_H_INCLUDED
        

LinkedDeque.h 头文件

#ifndef LINKEDDEQUE_H_INCLUDED
#define LINKEDDEQUE_H_INCLUDED

#include "Entitys.h"

//************************************************************************************************************************************************************************
//
//      类名：链表双端队列(LinkedDeque)
//
//      概述：一个可复用的链表双端队列，存储结构采用链表实现，支持任意类型数据（模板泛型）。
//
//      说明：因为采用链表存储结构，队列的容量没限制，入队出队时间复杂度为O(1)
//
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//
//                                                                 队列节点结构体(QueueNode)
//
//========================================================================================================================================================================
template <typename T>
struct DequeNode
{
    T data;             //队列节点数据
    DequeNode* prev;    //前一个队列节点指针
    DequeNode* next;    //下一个队列节点指针
};

//========================================================================================================================================================================
//
//                                                               链表双端队列结构体(LinkedDeque)
//
//========================================================================================================================================================================
template <typename T>
struct LinkedDeque{
    //------------------------------------------------------------------------------------------------------
    //                                          私有成员                                                ||
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）   ||
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        DequeNode<T> *head = nullptr;   // 队列头指针
        DequeNode<T> *tail = nullptr;   // 队列尾指针
        int qty = 0;                    // 用于跟踪队列中的元素数量

        //---------------声明私有成员函数---------------



    //------------------------------------------------------------------------------------------------------
    //                                          公共成员                                                ||
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）     ||
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        LinkedDeque() {
            qty = 0;
        }

        int isEmpty();                      // 判断队列是否为空
        int isFull();                       // 判断队列是否已满
        T getHead();                        // 获取队列头元素（不弹出）
        T getTail();                        // 获取队列尾元素（不弹出）
        void pushHead(const T& value);   // 队头入队（左入）
        void pushTail(const T& value);    // 队尾入队（右入）
        T popHead();                      // 队头出队（左出）
        T popTail();                       // 队尾出队（右出）
        int getSize();                  // 获取队列大小
        void print();                     // 打印队列数据
        void destroyDeque();              // 手动销毁整个队列（防止内存泄漏）

        // 析构函数：自动销毁栈，避免内存泄漏
        ~LinkedDeque() {
            destroyDeque();
        }
};

#endif // LINKEDDEQUE_H_INCLUDED
                

LinkedDeque.cpp 程序代码

#include <iostream>
#include"LinkedDeque.h"

//---------------实现公共成员函数---------------

// 判断队列是否为空
template <typename T>
int LinkedDeque<T>::isEmpty()
{
    return qty == 0;
}

// 判断队列是否已满
template <typename T>
int LinkedDeque<T>::isFull()
{
    return -1;
}

// 获取队列头元素（不弹出）
template <typename T>
T LinkedDeque<T>::getHead()
{
    if (isEmpty()) {
        return T();
    }
    return head->data;
}

// 获取队列尾元素（不弹出）
template <typename T>
T LinkedDeque<T>::getTail()
{
    if (isEmpty()) {
        return T();;
    }
    return tail->data;
}

// 队头入队（左入）
template <typename T>
void LinkedDeque<T>::pushHead(const T& value)
{
    DequeNode<T> *p = new DequeNode<T>;
    p->data = value;
    p->prev = nullptr;
    if(isEmpty())
    {
        p->next = nullptr;
        head = p;
        tail = p;
    }
    else
    {
        p->next = head;
        head->prev = p;
        head = p;
    }

    qty++;
}

// 队尾入队（右入）
template <typename T>
void LinkedDeque<T>::pushTail(const T& value)
{
    DequeNode<T> *p = new DequeNode<T>;
    p->data = value;
    p->next = nullptr;
    if(isEmpty())
    {
        p->prev = nullptr;
        head = p;
        tail = p;
    }
    else
    {
        p->prev = tail;
        tail->next = p;
        tail = p;
    }

    qty++;
}

// 队头出队（左出）
template <typename T>
T LinkedDeque<T>::popHead()
{
    T value;
    if(isEmpty())
    {
        printf("队列为空，无法出队。\n");
        return T();
    }

    DequeNode<T> *p = head;
    head = p->next;
    head->prev = nullptr;
    value = p->data;
    delete(p);
    qty--;

    return value;
}

// 队尾出队（右出）
template <typename T>
T LinkedDeque<T>::popTail()
{
    T value;
    if(isEmpty())
    {
        printf("队列为空，无法出队。\n");
        return T();
    }

    DequeNode<T> *p = tail;
    tail = p->prev;
    tail->next = nullptr;
    value = p->data;
    delete(p);
    qty--;

    return value;
}

// 获取队列大小
template template <typename T>
int LinkedDeque<T>::getSize()
{
    return qty;
}

// 打印队列数据
template <typename T>
void LinkedDeque<T>::print()
{
    printf("队列内容：");

    DequeNode<T> *p = head;
    if(p == nullptr)
    {
        printf("队列为空！无法遍历。\n");
        return;
    }
    while(p != nullptr)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

// 销毁整个栈（防止内存泄漏）
template <typename T>
void LinkedDeque<T>::destroyDeque()
{
    while(head != nullptr)
    {
        DequeNode<T> *p = head;
        head = p->next;
        delete(p);
        qty--;
    }
    printf("\n===== 队列内存已全部释放 =====\n");
}

// 显式实例化常用类型（避免链接错误，可选）
template class LinkedDeque<int>;
template class LinkedDeque<char>;
template class LinkedDeque<float>;
template class LinkedDeque<std::string>;
template class LinkedDeque<Student>; // 新增：显式实例化Student类型
template class LinkedDeque<Pos>; // 新增：显式实例化Pos类型
template class LinkedDeque<PrintTask>; // 新增：显式实例化PrintTask类型
        

main.cpp 测试代码

#include "LinkedDeque.h"
#include <iostream>

int main() {
    LinkedDeque<int> deques;

    // 1. 尾入队测试
    printf("\n=== 尾入队测试 ===\n");
    deques.pushTail(1);
    deques.pushTail(2);
    deques.pushTail(3);
    deques.pushTail(4);
    deques.pushTail(5);
    printf("尾入队1、2、3、4、5后：\n");
    deques.print();

    // 1. 头入队测试
    printf("\n=== 头入队测试 ===\n");
    deques.pushHead(6);
    deques.pushHead(7);
    deques.pushHead(8);
    deques.pushHead(9);
    deques.pushHead(10);
    printf("头入队6、7、8、9、10后：\n");
    deques.print();

    // 2. 头出队测试
    printf("\n=== 头出队测试 ===\n");
    printf("出队3次：");
    printf("%d ",deques.popHead());
    printf("%d ",deques.popHead());
    printf("%d \n",deques.popHead());
    printf("出队后");
    deques.print();

    // 2. 尾出队测试
    printf("\n=== 尾出队测试 ===\n");
    printf("出队3次：");
    printf("%d ",deques.popTail());
    printf("%d ",deques.popTail());
    printf("%d \n",deques.popTail());
    printf("出队后");
    deques.print();
    
    return 0;
}

输出结果

=== 尾入队测试 ===
尾入队1、2、3、4、5后：
队列内容：1 2 3 4 5

=== 头入队测试 ===
头入队6、7、8、9、10后：
队列内容：10 9 8 7 6 1 2 3 4 5

=== 头出队测试 ===
出队3次：10 9 8
出队后队列内容：7 6 1 2 3 4 5

=== 尾出队测试 ===
出队3次：5 4 3
出队后队列内容：7 6 1 2

===== 队列内存已全部释放 =====
    

六、注意事项

七、应用场景

• 滑动窗口最大值 / 最小值：利用双端队列维护窗口内的候选元素，队首始终是当前窗口的最大值 / 最小值，时间复杂度优化到 O (n)。
• 回文判断：将字符串字符依次加入双端队列，然后从两端同时取出字符比较，全部相等则为回文。
• 任务调度：支持 “插队”（队首插入）和 “末尾追加”（队尾插入）的任务队列，比如优先级不高的任务放队尾，紧急任务放队首。

八、总结

• 双端队列的本质是 “双向操作的线性结构”，突破了普通队列的单向操作限制，核心是高效维护队首和队尾的插入 / 删除。
• 链表实现：靠 “双向指针” 实现灵活操作，天然支持动态扩容。
• 关键原则：所有操作需优先处理 “空队列” 和 “仅一个元素” 的边界情况，避免指针 / 索引异常。

掌握这些原理后，你不仅能手写双端队列，还能根据实际场景选择最优的实现方式，也能理解算法题中双端队列的应用逻辑。